1. Field of the Invention
The present invention is a method of controlling access to the call completion on busy link service in a private telecommunication network.
2. Description of the Prior Art
The invention concerns private telecommunication networks. Such networks are formed of communication nodes connected together by links carrying calls and/or signaling. It applies equally to physical private networks (which are formed of dedicated connections), virtual private networks and hybrid networks combining the two solutions. In the remainder of the description the invention is described with reference to one example of a private network with signaling, but it applies more generally to other private networks.
The Dijkstra algorithm is described in the literature on algorithms and calculates the shortest path between tow nodes in a graph. In operation, the algorithm considers a graph G with N nodes, which is valued, i.e., each existing path of which between two nodes i and j is assigned a value or weight I(i,j); considers an outgoing node s of the graph G and in incoming node d; and seeks a path minimizing I1 (s,d), the distance from s to d, i.e., the sum of the values of the connections s to d. S is the subgraph of G formed of the nodes x for which the minimum path to s is known, and S is its complement. Γi is the set of nodes adjoining a given node i.
Initially the subgraph S contains only the node s, and S contains all the other nodes, assigned the following initial values:                π(s, i)=l(s, i) for ∈Γs, the parent node being s;        π(s, i)=∞, for the other nodes, which have no parent node.        
An iteration of the algorithm is effected in the following manner.
If S is empty, or if it contains only nodes i with π(s, i)=∞, the algorithm has finished.
Otherwise, the node n of S is considered which is nearest the originating node, i.e. the node which minimizes π(s, i), i ∈ S; this node is taken from S and placed in S.
The nodes adjacent this node n are then considered and the algorithm calculatesπ(s, n)=l(n, j),j∈Γn and l∈ S; 
If this quantity is less than π(s, j), then π(s, j) is updated:π(s, j):=π(s, n)+l(n, j) and the parent node of is also updated, which becomes n.
This operation is carried out for all the nodes of Γn, after which S is reordered.
In this way, all the nodes of the graph are progressively added to S, in order of increasing path length. To find a path to a given node d, the algorithm can be interrupted before it finishes, since the destination node a has been added to the subgraph S.
The validity of the algorithm is demonstrated by the following reductio ad absurdum argument. Consider the node n nearest S which must be added to S. If there is a nearer path, that path starts from s and arrives at n and has a first node m in S. Then:π(s, m)+π(m, n)<π(s, n) and, since π(m, n) is positive or zero:π(s, m)<p(s, n) which contradicts the hypothesis. It is also clear that π(s, m) has been calculated in a preceding iteration, when adding the parent of m to S.
The document by J. Eldin and K. P. Lathia “Le RNIS appliqué au Centrex et au réseaux privés virtuels” [The ISDN applied to Centrex and to virtual private networks] contains a description of physical private networks and virtual private networks. As explained in the document, in a physical private network the various sites or nodes are connected by dedicated circuits but in a virtual private network each node is connected to the local switch nearest the public network, where appropriate software sets up the connections on demand. There are two variants of the virtual private network: on the one hand, semi-permanent connections can be provided, which are set up without dialing as soon as any of the nodes requires the circuit, and which always connect the same two points. Such may be the case in particular for signaling connections in an application on an integrated services digital network. On the other hand, switched connections can be provided, which can set up only by dialing.
The remainder of the description considers only physical or virtual private networks formed of nodes connected by links, which can be any type: dedicated connections, or links using an external network; the latter can be of any type—the public switched network, a public land mobile network, an integrated services digital network, etc. FIG. 1 shows one example of a private network of this kind. This network includes, for example, nodes 1 to 6; nodes 1, 2 and 4 to 6 are connected to the public network 8 by circuit groups 11, 12 and 14 to 16. The nodes are interconnected by links formed of private connections, shown in bold in the figure, or, as in the case of the link between nodes 5 and 6, by a link comprising only a signaling connection. For a digital link, each private connection comprises at least one access, formed by a signaling connection and a plurality of B channels. The link between nodes 5 and 6 in FIG. 1, and likewise the link between nodes 1 and 2, comprises a signaling connection and no B channel; this is typical of a node corresponding to a branch office, for which the volume of traffic is not very high.
The problem of overflow, i.e. the problem of a call request that cannot be satisfied by the network because its resources are congested, arises in private networks. This problem can arise if the private links of the private network have a fixed capacity, rather than a capacity which is allocated dynamically and which is less than the possible maximum volume of traffic. Completing the corresponding call using the public network is known in itself. In other words, if a user at node 2 wants to contact a user at node 6, and if the private network is congested and cannot complete the call, the call is completed via circuit groups 12 and 16 and the public network. This can be the case, for example, if the connection between nodes 2 and 4 is congested. In FIG. 1, reference numeral 10 shows schematically a call of this kind via the public network. Overflow may also be necessary if the link in question has no B channel, as in the case of node 6 in FIG. 1.
One problem is the cost of such overflows. Because of this cost, rules can be defined denying certain users or certain categories of user access to this service.
The prior art also provides a CCBL (call completion on busy link) service which provides automatic callback if a link of the private network is busy or congested. In this case, the calling user is put on hold for as long as the private network link is congested and is called back when sufficient resources are released to route the call. In existing private networks this CCBL service is provided without distinguishing between users.
This solution gives rise to the following problem in the case of overflows to the public network. If an overflow is necessary to reach the called user, and if the rights or monitored cost of the user are less than the charge incurred for the overflow, the CBBL service might never call back. This is the case in particular for users who have no overflow rights. The CCBL request therefore remains unsatisfied.
The invention proposes a solution to this new problem. It prevents users being queued unnecessarily and prevents congestion of the private network by CCBL requests that cannot be satisfied. The invention applies particularly to the routing solution proposed in our application filed the same day as this application with the title “Routing of calls with overflow in a private network”. It also applies to routes chosen by a separate process and which enables one or more overflows to a public network.